/*** 
 * @Author: wangkai
 * @Date: 2025-01-18 18:31:01
 * @LastEditTime: 2025-01-28 22:13:17
 * @LastEditors: your name
 * @Description: 单链表的一些增删查改的接口的实现及测试
 * @FilePath: \List\List.cpp
 * @可以输入预定的版权声明、个性签名、空行等
 */
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
// 一切涉及到指针的操作都要注意传递参数时是传值还是传址
// 涉及到遍历的问题时，需要注意是否对链表的头指针进行了修改，一般要创建一个局部变量保存传入的参数

typedef int TypeListNode;
struct ListNode
{
    TypeListNode val;
    ListNode* next;
};

/*** 
 * @description: 单链表的增加节点的接口
 * @param {TypeListNode} data
 * @return {ListNode*}
 */
ListNode* BuyNode(TypeListNode data)
{
    ListNode* T=(ListNode*)malloc(sizeof(ListNode));
    if(T==nullptr)
    {
        cout<<"malloc failed"<<endl;
        return nullptr;
    }
    T->val=data;
    T->next=nullptr;
    return T;
}

//初始化空链表
void InitListNode(ListNode*& T,int data=0)
{
    T=BuyNode(data);    
}

//销毁单链表的所有节点
void ListNodeDestroy(ListNode*& T)
{
    if(!T)return;
    while(T)
    {
        ListNode* temp=T;
        T=T->next;
        free(temp);
    }
    T=nullptr;
}

//单链表的插入
void ListNodeInsert(ListNode*& T,TypeListNode data)
{
    if(T==nullptr)InitListNode(T,data);
    else 
    {
        //每次插入都需要找到链表的最后一个节点
        ListNode* cur=T;
        while(cur->next!=nullptr)cur=cur->next;
        cur->next=BuyNode(data);
    } 
}

//单链表的查找值的接口，成功返回true，否则返回false
bool ListNodeSearch(ListNode*& T, TypeListNode data)
{
    if(T==nullptr)
    {
        cout<<"链表为空，无法查找"<<endl;
        return false;
    }
    while(T)
    {
        if(T->val==data)return true;
        T=T->next;
    }
    return false;
}

//单链表的更改节点的值的接口
//defaultchangenumber默认只修改一个链表节点的值，传true时全部修改
void ListNodeChange(ListNode*& T, TypeListNode data,TypeListNode changedata,bool defaultchangenumber=false)
{
    ListNode*cur=T;
    if(!defaultchangenumber)
    {
        while(cur)
        {
            if(cur->val==data)
            {
                cur->val=changedata;
                break;
            }
            cur=cur->next;
        }
    }
    else
    {
        while(cur)
        {
            if(cur->val==data)
            {
                cur->val=changedata;
            }
            cur=cur->next;
        }
    }
}

//单链表的删除相同值的接口
//DeleteAll为false时只删除一个值相同节点(优先删除值靠前的)，true时删除所有值相同的节点
void ListNodeDelete(ListNode*& T,TypeListNode data,bool DeleteAll=false)
{
    while(T!=nullptr&&T->val==data)
    {
        ListNode* tmp=T;
        T=T->next;
        free(tmp);
        if(!DeleteAll)return;
    }

    if (T==nullptr)return;
    
    ListNode* prev=T;
    ListNode* cur=T->next;
    while(cur)
    {
        if(cur->val==data)
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
            if(!DeleteAll)return;
        }
        prev=cur;
        cur=cur->next;
    }
}

//单链表的数据个数
int ListSize(ListNode* T)
{
    if(!T)return 0;
    int count=0;
    ListNode*cur=T;
    while(cur)
    {
        count++;
        cur=cur->next;
    }
    return count;
}

//判断单链表是否为空
bool ListNodeEmpty(ListNode* T)
{
    if(T==nullptr)return true;
    return false;
}

//输出单链表的所有值
void PrintList(ListNode* T)
{
    if(T==nullptr)
    {
        std::cout<<"链表为空，请正确传参数\n";
        return;
    }
    while(T)
    {
        std::cout<<T->val<<" ";
        if(!(T->next))break;
        T=T->next;
    }
    std::cout<<endl;
}

//测试接口是否可以正确使用
void test()
{
    ListNode* l;
    InitListNode(l);
    ListNodeInsert(l,1);
    ListNodeInsert(l,2);
    ListNodeInsert(l,3);
    ListNodeInsert(l,4);
    ListNodeInsert(l,5);
    ListNodeInsert(l,1);
    ListNodeInsert(l,4);
    ListNodeInsert(l,3);
    ListNodeInsert(l,10);
    PrintList(l);
    // if(ListNodeSearch(l,1))cout<<"value 1 is exist"<<endl;
    // else cout<<"value 1 is not exist"<<endl;
    // ListNodeChange(l,1,20,true);
    // if(ListNodeEmpty(l))cout<<"List1 is empty"<<endl;
    // ListNodeDestroy(l);
    // if(ListNodeEmpty(l))cout<<"List is empty"<<endl;
    ListNodeDelete(l,10);
    PrintList(l);
}

//主函数
// int main()
// {
//     test();
//     return 0;
// }
#include <iostream>
#include <vector>
using namespace std;

//key-value结构
//哈希表的关键思想是使用哈希函数，将键key 映射到对应表的某个区块中。
int main()
{
    vector<int> p;
    int sum=0;
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    for(int i=0;i<10;i++)
    {
        sum+=a[i];
        p[i]=sum;
    }
    int s=p[3]-p[1];
    cout<<"hello world777";
}

//leetcode刷题
// #include <iostream>
// #include <vector>
// #include <map>
// using namespace std;
// class Solution {
// public:
//     int buttonWithLongestTime(vector<vector<int>>& events) {
//         int idx=events[0][0],max_diff=events[0][1];
//         for(int i=1;i<events.size();i++)
//         {
//             vector<int> p=events[i-1];
//             vector<int> q=events[i];
//             int d=q[1]-p[1];
//             if(d>max_diff || d==max_diff && q[0]<idx)
//             {
//                 idx=q[0];
//                 max_diff=d;
//             }
//         }
//         return idx;
//     }
// };
// class Solution {
// public:
//     vector<int> getRow(int rowIndex) {
//         vector<vector<int>> retvector(rowIndex+1, vector<int>(rowIndex+1));
//         retvector[0][0]=1;
//         for(int i=1;i<=rowIndex;i++)
//         {
//             retvector[i][0] = retvector[i][i] = 1; 
//             for(int j=1;j<i;j++)
//             retvector[i][j]=retvector[i-1][j-1]+retvector[i-1][j];
//         }
//         return retvector[rowIndex];
//     }
// };
// class Solution {
// public:
//     string intToRoman(int num) {
//         vector<string> Rom={
//             "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"
//         };
//         vector<int> symbol={
//             1000,900,500,400,100,90,50,40,10,9,5,4,1
//         };
//         string retstring;
//         for(int i=0;i<symbol.size();i++)
//         {
//             while(num>=symbol[i])
//             {
//                 num-=symbol[i];
//                 retstring+=Rom[i];
//             }
//         }
//         return retstring;
//     }
// };
// unordered_map<char, int> ROMAN = {
//     {'I', 1},
//     {'V', 5},
//     {'X', 10},
//     {'L', 50},
//     {'C', 100},
//     {'D', 500},
//     {'M', 1000},
// };
// class Solution {
// public:
//     int romanToInt(string s) {
//         int ans=0;
//         for(int i=1;i<s.size();i++)
//         {
//             int x=ROMAN[s[i-1]],y=ROMAN[s[i]];
//             ans+=x<y?-x:x;
//         }
//         return ans+ROMAN[s.back()];
//     }
// };
// int main()
// {
//     // Solution s;
//     // int row;cin>>row;
//     // auto vet=s.getRow(row);
//     return 0;
// }